// @algorithm @lc id=152 lang=cpp 
// @title maximum-product-subarray


// #define print(...)
// @test([2,3,-2,4])=6
// @test([-2,0,-1])=0
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        vector<int> upper(nums), lower(nums);
        for(int i=1; i<nums.size(); i++){
            upper[i] = max(nums[i], max(upper[i-1]*nums[i], lower[i-1]*nums[i]));
            lower[i] = min(nums[i], min(upper[i-1]*nums[i], lower[i-1]*nums[i]));
        }
        return *max_element(upper.begin(), upper.end());
    }
};